A content addressable memory or CAM may be viewed conceptually as a search engine that is fabricated from hardware rather than software. Software search engines, which are algorithmically based, tend to be substantially slower than hardware-based CAMs. CAMs can be formed from arrays of conventional semiconductor memory, for example, static random access memory (SRAM), together with additional comparison circuitry that enables a search operation to finish in a single system clock cycle. One routine search-intensive task that benefits significantly from CAM is the address lookup task performed in routers such as Internet routers. Other typical uses of CAM include caches such as processor caches, translation look aside buffers (TLBs), segment lookaside buffers (SLBs) used in the industry for processor memory management, effective to real address translators (ERATs), database accelerators, and data compression applications.
A conventional CAM is configured as an array of individual CAM core cells. A typical binary CAM core cell supports the storage and searching of binary bits, namely zero or one (0, 1). A single CAM cell stores a binary bit in what is referred to as a “true and complement” data form, meaning a zero will be stored in both a zero state and a complemented one state within the core cell. In contrast, a one will be stored both as a one state and a complemented zero state. Horizontal and vertical rows of NOR-based architecture CAM core cells can be configured to form a large CAM array. In such an array, the CAM size is described first by the number of horizontal cells which is also called the word size. And second, the CAM size is described by the vertical cell count which corresponds to the number of words stored and available during a compare operation. In a compare operation, input data is simultaneously compared against each word stored in the CAM.
CAM core cells include both storage and comparison circuitry. Search lines runs vertically through the CAM cell and broadcast the search data to all CAM cells at the same time. Match lines run horizontally across the array and indicate whether or not the search data matches a particular row's word. In more detail, an activated match line (an active high logic state) indicates a match and a deactivated match line (a low logic state) indicates a mismatch for a particular word corresponding to that match line. These match lines which describe the output of the CAM array are typically coupled to memory devices such as SRAMs or dynamic random access memories (DRAMs) to provide the actual output match data.
A CAM search operation begins with precharging all match lines high, thus placing all match lines temporarily in the match state. Next, the search lines broadcast the search data in binary vertically simultaneously across all words of the array. Next, each CAM core cell compares its stored single binary data against the bit on its corresponding search lines. Cells with matching data do not affect the corresponding word's match line, but cells with a mismatch pull down the corresponding word's match line. The aggregate result is that the match line of any word having at least one bit mismatch is pulled low. All other match lines remain activated (precharged high). Usually almost all match lines are driven low thus indicating mismatches for the words corresponding to those match lines. Typically, one or a small number of match lines will remain high to indicate a matching word or words. Finally, the match lines that remain high, indicating a match, are used as the input to an address lookup memory that is coupled to the CAM. The data thus addressed in the address lookup memory is then read from the address lookup memory as output data to provide the ultimate result of the search.
CAM structures typically match a given input data pattern against all bits of all words or entries to determine a match. However, in some circumstances, it is desirable to match on different subsets of bits per word, instead of all bits of the word. In this situation a compare mask can be used to provide compares on subsets of bits per word or to provide bitwise compares. By masking against each individual bit of the input data, any specific bit or collection of bits of the word data may be compared or masked out and ignored as desired.
What is needed is a method and apparatus for selecting the operating characteristics of a CAM.